package com.hyb.algorithm.data.struct.backtrack;

import java.util.ArrayList;
import java.util.List;

/**
 * 216. 组合总和 III
 * https://leetcode.cn/problems/combination-sum-iii/description/
 * @author: ybhu
 * @create: 2023/12/29 17:58
 */
public class CombinationSumIII {
    private  List<List<Integer>>  res;
    public List<List<Integer>> combinationSum3(int k, int n) {

        res=new ArrayList<List<Integer>>();

        List<Integer> list=new ArrayList<>();

        backTrack(n,k,1,list);

        return res;
    }


    public void backTrack(int target,int k,int start,List<Integer> list){

        //递归终止条件
        if(list.size()==k){
            if(target==0){
                res.add(new ArrayList(list));
            }
            return;
        }


        for(int index=start;index<=9;index++){
            if(target-index>=0){
                list.add(index);
                backTrack(target-index,k,index+1,list);
                list.remove(list.size()-1);
            }else{
                break;
            }
        }

    }
}
